import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-07-30
 * Time: 0:22
 */
public class MySort {
    // 归并排序---递归
    public static void mergeSort(int[] arr){
        merge(arr,0,arr.length-1);
    }

    public static void merge(int[] arr,int first,int end){
        if(first>=end){
            return;
        }
        int in=(first+end)/2;
        merge(arr,first,in);
        merge(arr,in+1,end);
        towSort(arr,first,end);
    }

    //合并两个有序数组
    public static void towSort(int[] arr,int first,int end){
        int in=(first+end)/2;
        int a=first;
        int b=in+1;
        int i=0;
        int[] brr=new int[end-first+1];
        while(a<=in&&b<=end){
            if(arr[a]<=arr[b]){
                brr[i]=arr[a];
                a++;
            }
            else{
                brr[i]=arr[b];
                b++;
            }
            i++;
        }
        if(a>in){
            while(b<=end){
                brr[i]=arr[b];
                b++;
                i++;
            }
        }
        else{
            while(a<=in){
                brr[i]=arr[a];
                a++;
                i++;
            }
        }
        for ( i = 0; i<brr.length; i++) {
            arr[i+first]=brr[i];
        }
    }

    public static void fun(int[] arr,int i,int j){
        int n=arr[i];
        arr[i]=arr[j];
        arr[j]=n;
    }

    // 归并排序---非递归
    public static void mergeSortNor(int[] arr){
        Stack<Integer> stack=new Stack();
        LinkedList<Integer> queue=new LinkedList();
        int first=0;
        int end=arr.length-1;
        queue.offer(first);
        queue.offer(end);
        int in;
        while((first!=arr.length-1)||(end!=arr.length-1)){
            first=queue.poll();
            end=queue.poll();
            in=(first+end)/2;
            stack.push(first);
            stack.push(end);
            if(first<=in) {
                queue.offer(first);
                queue.offer(in);
            }
            if(in+1<=end) {
                queue.offer(in + 1);
                queue.offer(end);
            }
        }
        while(!stack.isEmpty()){
           end=stack.pop();
           first=stack.pop();
           towSort(arr,first,end);
        }
    }

    // 计数排序
    public static void countSort(int[] arr){
        int max=arr[0];
        int min=arr[0];
        for (int i = 0; i <arr.length; i++) {
            if(arr[i]>max)
                max=arr[i];
            if(arr[i]<min)
                min=arr[i];
        }
        int[] brr=new int[max-min+1];
        for (int i = 0; i < arr.length; i++) {
            brr[arr[i]-min]++;
        }
        for(int i=0,n=0;i<brr.length;i++){
            while(brr[i]!=0){
                arr[n++]=i+min;
                brr[i]--;
            }
        }
    }
}
